package com.chapter3.search;

import java.util.Iterator;
import java.util.Queue;
import java.util.concurrent.PriorityBlockingQueue;

/** 
 * @ClassName: RedBlackBST 
 * @Description: 红黑树
 * @author minjun minjun@bw30.com
 * @date 2015-2-21 下午7:22:19 
 *  
 */
public class RedBlackBST<K extends Comparable<K>,V> extends AbstractST<K, V>{
	
	private static final boolean RED=true;
	
	private static final boolean BLACK=false;
	
	private Node root;
	
	private class Node{
		int sz;
		K k;
		V v;
		Node left,right;
		boolean color;
		public Node(int sz, boolean color,K k, V v) {
			super();
			this.sz = sz;
			this.color = color;
			this.k=k;
			this.v=v;
		}
	}
	
	public int size(){
		return size(root);
	}

	/** 
	* @Title: size 
	* @Description: 获取指定节点的大小
	* @param @param root2
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws 
	*/ 
	private int size(Node node) {
		return node==null?0:node.sz;
	}

	@Override
	public void put(K k, V v) {
		root=put(k, v,root);
		root.color=BLACK;
	}

	/** 
	* @Title: put 
	* @Description: 插入元素
	* @param @param k
	* @param @param v
	* @param @param node
	* @param @return    设定文件 
	* @return Node    返回类型 
	* @throws 
	*/ 
	private Node put(K k, V v, Node node) {
		if(node==null){
			//创建一个红节点跟在后面
			return new Node(1,RED,k,v);
		}
		int cmp=k.compareTo(node.k);
		if(cmp<0){
			node.left=put(k, v, node.left);
		}else if(cmp>0){
			node.right=put(k, v, node.right);
		}else{
			node.v=v;
		}
		//调整树结构
		if(!isRed(node.left)&&isRed(node.right)){
			node=rotateLeft(node);
		}
		if(isRed(node.left)&&isRed(node.left.left)){
			node=rotateRight(node);
		}
		if(isRed(node.left)&&isRed(node.right)){
			flipColors(node);
		}
		//计算大小
		node.sz=size(node.left)+size(node.right)+1;
		return node;
	}
	
	private boolean isRed(Node node){
		return node==null?false:(node.color==RED);
	}

	/** 
	* @Title: flipColors 
	* @Description: 将所有红节点变为黑节点，并将父节点改为红节点
	* @param @param node
	* @throws 
	*/ 
	private void flipColors(Node node) {
		node.left.color=BLACK;
		node.right.color=BLACK;
		node.color=RED;
	}

	/** 
	* @Title: rotateLeft 
	* @Description: 左旋
	* @param @param node
	* @param @return    设定文件 
	* @return Node    返回类型 
	* @throws 
	*/ 
	private Node rotateLeft(Node node) {
		//改变节点结构
		Node n=node.right;
		node.right=n.left;
		n.left=node;
		//重设红黑值
		n.color=node.color;
		node.color=RED;
		//重置树大小
		n.sz=node.sz;
		node.sz=size(node.left)+size(node.right)+1;
		//返回重置之后新的根节点
		return n;
	}
	
	/** 
	* @Title: rotateRight 
	* @Description: 右旋
	* @param @param node
	* @param @return    设定文件 
	* @return Node    返回类型 
	* @throws 
	*/ 
	private Node rotateRight(Node node) {
		Node n=node.left;
		node.left=n.right;
		n.right=node;
		n.color=node.color;
		node.color=RED;
		n.sz=node.sz;
		node.sz=size(node.left)+size(node.right)+1;
		return n;
	}

	@Override
	public V get(K k) {
		return get(k,root);
	}

	/** 
	* @Title: get 
	* @Description: 递归获取指定元素 
	* @param @param k
	* @param @param root2
	* @param @return    设定文件 
	* @return V    返回类型 
	* @throws 
	*/ 
	private V get(K k, Node node) {
		if(node==null) return null;
		int cmp=k.compareTo(node.k);
		if(cmp>0){
			return get(k, node.right);
		}else if(cmp<0){
			return get(k, node.left);
		}else{
			return node.v;
		}
	}

	@Override
	public void delete(K k) {
		
	}

	@Override
	public boolean contains(K k) {
		return false;
	}

	@Override
	public Iterable<K> keys() {
		Queue<K> queue=new PriorityBlockingQueue<K>();
		return fill(queue,root);
	}

	/** 
	* @Title: fill 
	* @Description: TODO(这里用一句话描述这个方法的作用) 
	* @param @param queue
	* @param @param root2
	* @param @return    设定文件 
	* @return Iterable<K>    返回类型 
	* @throws 
	*/ 
	private Iterable<K> fill(Queue<K> queue, Node node) {
		if(node==null) return null;
		fill(queue, node.left);
		queue.add(node.k);
		fill(queue,node.right);
		return queue;
	}

	@Override
	public Iterator<K> iterator() {
		return keys().iterator();
	}
	
}
